package problems.contest;

import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * 第 318 场周赛
 * <p>https://leetcode.cn/contest/weekly-contest-318/</p>
 *
 * @author habitplus
 * @since 21:57, 2022/11/6
 */
public class WCT318 {

    public static void main(String[] args) {
        System.out.println(new WCT318().totalCost(new int[] {31,25,72,79,74,65,84,91,18,59,27,9,81,33,17,58}, 11, 2));
    }


    /**
     * T1|6229. 对数组执行操作
     * <p>https://leetcode.cn/problems/apply-operations-to-an-array/</p>
     */
    public int[] applyOperations(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n - 1; ++i) {
            if (nums[i] == nums[i + 1]) {
                nums[i] = 2 * nums[i];
                nums[i + 1] = 0;
            }
        }

        int k = 0;
        int[] arr = new int[n];

        for (int i = 0; i < n; ++i) {
            if (nums[i] != 0) {
                arr[k++] = nums[i];
            }
        }

        return arr;
    }


    /**
     * T2|6230. 长度为 K 子数组中的最大和
     * <p>https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/</p>
     */
    public long maximumSubarraySum(int[] nums, int k) {
        long sum = 0;
        long ret = 0;
        int n = nums.length;
        int pre = 0;
        HashSet<Integer> set = new HashSet<>();

        for (int i = 0; i < n; ++i) {

            while (set.contains(nums[i]) || set.size() >= k) {
                set.remove(nums[pre]);
                sum -= nums[pre];
                ++pre;
            }

            set.add(nums[i]);
            sum += nums[i];

            if (set.size() == k) {
                ret = Math.max(ret, sum);
            }

        }

        return ret;
    }


    /**
     * T3|6231. 雇佣 K 位工人的总代价
     * <p>https://leetcode.cn/problems/total-cost-to-hire-k-workers/</p>
     */
    public long totalCost(int[] costs, int k, int candidates) {
        PriorityQueue<Integer> leftQue = new PriorityQueue<>(Integer::compareTo);
        PriorityQueue<Integer> rightQue = new PriorityQueue<>(Integer::compareTo);
        int n = costs.length;
        int left = 0;
        int right = n - 1;

        while (left < candidates) {
            leftQue.add(costs[left++]);
        }

        while (right >= left && right >= n - candidates) {
            rightQue.add(costs[right--]);
        }

        long ret = 0;
        int lk, rk;
        while (k > 0) {

            lk = leftQue.peek() == null ? -1 : leftQue.peek();
            rk = rightQue.peek() == null ? -1 : rightQue.peek();

            if (rk == -1) {
                // 取左边
                leftQue.poll();
                ret += lk;

                if (left <= right) {
                    leftQue.add(costs[left++]);
                }
            } else if (lk == -1) {
                // 取右边
                rightQue.poll();
                ret += rk;

                if (left <= right) {
                    rightQue.add(costs[right--]);
                }
            } else if (lk > rk) {
                // 取右边
                rightQue.poll();
                ret += rk;

                if (left <= right) {
                    rightQue.add(costs[right--]);
                }
            } else {
                // 取左边
                leftQue.poll();
                ret += lk;

                if (left <= right) {
                    leftQue.add(costs[left++]);
                }
            }

            --k;
        }

        return ret;
    }
}
